package 剑指II;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-03
 **/

public class Jz015字符串中的所有变位词 {

    /**
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     * 变位词 指字母相同，但排列不同的字符串。
     * <p>
     * 示例 1:
     * 输入: s = "cbaebabacd", p = "abc"
     * 输出: [0,6]
     * 解释:
     * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
     * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。
     *  示例 2:
     * 输入: s = "abab", p = "ab"
     * 输出: [0,1,2]
     * 解释:
     * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
     * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
     * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。
     *  
     * 提示:
     * 1 <= s.length, p.length <= 3 * 104
     * s 和 p 仅包含小写字母
     */

    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> result = new ArrayList<>();
        int left = 0;
        int right = 0;
        char[] bigArr = s.toCharArray();
        char[] smallArr = p.toCharArray();
        int count = 0;
        int[] arr = new int[26];
        for (char c : smallArr) {
            if (arr[c - 'a'] == 0) {
                count++;
            }
            arr[c - 'a']++;
        }

        while (right < bigArr.length) {
            char c = bigArr[right++];

            while (left < right && arr[c - 'a'] <= 0) {
                arr[bigArr[left] - 'a']++;
                if (arr[bigArr[left] - 'a'] == 1) {
                    count++;
                }
                left++;
            }

            // 双标对其,重新开始
            if (left > right) {
                right++;
                continue;
            }

            // 可以吃入
            arr[c - 'a']--;
            if (arr[c - 'a'] == 0) {
                count--;
            }
            if (count == 0) {
                result.add(left);
            }

        }

        return result;
    }

    public static void main(String[] args) {
        Jz015字符串中的所有变位词 n = new Jz015字符串中的所有变位词();
        List<Integer> result = n.findAnagrams("abab", "ab");
        System.out.println(result);
    }

}
